连号区间数
题目 连号区间数
思路分析
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int maxv=-0x3f3f3f,minv=0x3f3f3f;
for(int k=i;k<=j;k++){
maxv=max(maxv,a[k]);
minv=min(minv,a[k]);
}
if(maxv-minv==j-i)
cnt++;
}
}
cout<<cnt;
return 0;
}
其实大概也猜到了 三重循环 n=10000 应该还是会tle
再模拟一遍发现 k完全不需要 j在往后走时 直接确定了区间长度 区间长度确定了 只需要判断最大值与最小值的差值即可
两重循环 \(n^2\) 且j不走回头路 大概是2n 绰绰有余
这样来看 oi赛制还是有点难的 只能交一次 你不能根据报错来反思调整代码
不要抱着试一试的心态 大概估计出来了写法 再想想时间复杂度 还能怎么优化
实在想不出来 就算了呗 反正有一半的分
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++){
int maxv=-0x3f3f3f,minv=0x3f3f3f;
for(int j=i;j<=n;j++){
maxv=max(maxv,a[j]);
minv=min(minv,a[j]);
if(maxv-minv==j-i)
cnt++;
}
}
cout<<cnt;
return 0;
}
💬 评论